package com.dzu.medium;

import com.dzu.common.ListNode;

/**
 * @author ZhaoDong
 * @date 2023/1/11 10:26
 * @description 92. 反转链表 II
 */
public class Test92 {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(4);
        ListNode l5 = new ListNode(5);

        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;

//        ListNode l3 = new ListNode(1);
//        ListNode l5 = new ListNode(2);
//        l3.next = l5;

        System.out.println(reverseBetween2(l1, 2, 4));
    }

    public static ListNode reverseBetween2(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        for (int i = 1; i < left; i++) {
            pre = pre.next;
        }
        head = pre.next;
        for (int i = left; i < right; i++) {
            ListNode nex = head.next;
            head.next = nex.next;
            nex.next = pre.next;
            pre.next = nex;
        }
        return dummy.next;
    }

    /**
     * 1,2,3,4,5：整体思路，找到中间链表（2,3,4），将其反转（4,3,2），然后将反转后的中间链表的尾结点2（同中间链表一开始的头结点2）指向中间链表的后一个结点5。
     * 再将中间链表的前一个结点1的next指向反转后中间链表的头结点4（同中间链表反转前的尾结点）4
     * 最后就变成了：1,4,3,2,5
     * @param head
     * @param left
     * @param right
     * @return
     */
    public static ListNode reverseBetween(ListNode head, int left, int right) {

        ListNode tempHead = null;
        ListNode temp = head;
        int count = 1;
        while (temp != null) {

            // 找到要反转的链表的前一个
            if (count == left - 1) {
                tempHead = temp;
            }

            // 开始反转
            if (left == count) {
                ListNode per = null;
                // 反转链表的头结点
                ListNode start = temp;

                int c = right - left + 1;
                while (c != 0) {
                    ListNode next = temp.next;
                    temp.next = per;
                    per = temp;
                    temp = next;
                    c--;
                }
                // 中间链表反转完成，将中间链表的头结点的next指向中间链表结点的后一个
                start.next = temp;
                // 判断中间链表的上一个结点是否是null， 如果不是，将上一个结点next指向反转后的中间链表
                // 如果是，直接返回中间链表反转后的头结点
                if (tempHead != null) {
                    tempHead.next = per;
                    return head;
                } else {
                    return per;
                }
            }
            count++;
            temp = temp.next;
        }
        return null;
    }
}
